//
// Created by hitfy on 2018/5/1.
//

#include <bits/stdc++.h>

using namespace std;

int GetMin(int i, int j){
    return i < j ? i : j;
}
/**
 * @param n: An integer
 * @return: the nth prime number as description.
 */
int nthUglyNumber(int n) {
    // write your code here
    int index[3] = {0,0,0};
    int *humble = new int[n];
    humble[0] = 1;
    for(int i = 1; i < n; i++) {
        int a = humble[index[0]] * 2;
        int b = humble[index[1]] * 3;
        int c = humble[index[2]] * 5;
        int min = GetMin(a, GetMin(b, c));
        if(a == min) index[0]++;
        if(b == min) index[1]++;
        if(c == min) index[2]++;
        humble[i] = min;
    }
    return humble[n-1];
}

int main(){
    int n;
    scanf("%d", &n);
    printf("%d", nthUglyNumber(n));
    return 0;
}

/**
 4. 丑数 II

设计一个算法，找出只含素因子2，3，5 的第 n 小的数。

符合条件的数如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...
注意事项

我们可以认为1也是一个丑数
您在真实的面试中是否遇到过这个题？
样例

如果n = 9， 返回 10
挑战

要求时间复杂度为O(nlogn)或者O(n)
*/